//单链表的创建和使用
#include <stdio.h>
# include<malloc.h>
//定义一个链表结构体
typedef struct Node
{
    int data;
    struct Node * next;
}Node,*Link;
void print_list(Link head);
Link new_headlist(int length,int a[]);
Link new_downlist(int length,int a[]);
void length_list(Link head);
int insert_list(Link head,int i,int x);
int delete_list(Link head,int x);
void destory_list(Link head);
int judegeN_list(Link head);


int main (void)
{
    //单链表所包含的元素
    int a [] = {1,2,3,4,5,6};
    int n = sizeof(a)/sizeof (a[0]);
   // printf ("%d",n);
    Link head1;
    Link head2;

    //使用头插法创建单链表
   head1 = new_headlist(n,a);

   //使用尾插法创建单链表
   head2 = new_downlist(n,a);

   //遍历链表
   print_list(head1);
   print_list(head2);

   //求单链表元素个数;
    length_list(head1);

    //在链表中插入元素
    insert_list(head2,3,5);
    print_list(head2);

    //删除单链表中的某一个元素,只能删一个
    delete_list(head2,2);
     print_list(head2);

     //对整个单链表进行释放
     destory_list(head2);

     //判断一个链表是不是空表
     int judge = judegeN_list(head2);
     if (judge == 1)
     {
         printf ("该链表是空表\n");
     }



    return 0;
}
Link new_headlist(int length,int a[])
{
    //创建头指针并初始化
    Link head  = (Link)malloc(sizeof (Node));
    head->next = NULL;
    int i;
    //创建后续链表并赋值
    for (i = 0;i < length;i++)
    {
        Link node = (Link)malloc(sizeof(Node));
        node->data = a[i];
        node->next = head->next;
        head->next = node;
    }
    return head;

}
void print_list(Link head)
{
    Link p;
    p = head->next;
    while ( p != NULL){
    printf ("%d\n",p->data);
    p = p->next;
    }
    printf ("end\n");
}
Link new_downlist(int length,int a[])
{
    Link head  = (Link)malloc(sizeof (Node));
    head->next = NULL;
    //创建一个指向链表的中转指针
    Link rear;
    int i;
    rear = head;
    for (i = 0;i < length;i++)
    {
        Link node = (Link)malloc(sizeof (Node));
        node->data = a[i];
        rear->next = node;
        rear = rear->next;//相当于rear= node;
        node->next = NULL;//不将链表的next域赋值为空的话,可能会指向未知空间,打印时会出错;
    }
    return head;
}
void length_list(Link head)
{
    int count = 0;
    Link p = head->next;
    while (p != NULL){
        count++;
        p = p->next;//循环出口条件
    }
    printf ("单链表元素个数为:%d",count);
}
int insert_list(Link head,int i,int x)
{
    //先要找到第i位
    Link p = head->next;
    int count = 0;
    while (p!=NULL&& count<i-1)
    {
        count ++;
        p = p->next;
    }
    //找到第五位之后,开始插入
    if (p == NULL)
        return -1;
    else
    {
        Link node=(Link)malloc(sizeof(Node));
        node->data = x;
        node->next = p->next;
        p->next = node;
     }
     return 1;
}
int delete_list(Link head,int x)//找到链表中元素为x的节点,并删除
{
    //首先要确保head不为空表
    if(head == NULL || head->next == NULL)
        return -1;
    //使用pq两个指针,并保证其一前一后
    Link p,q;
     p = head;
     q = head->next;

     while (p != NULL)
     {
         if (q->data == x)
         {
             p->next = q->next;
             free(q);
             return 1;
         }
         else
         {
             p = q;
             q = q->next;
         }
     }
     return -1;
}
void destory_list(Link head)
{
    Link q;
    //从头结点开始一个一个释放
    while (head != NULL)
    {
        q = head;
        head = head->next ;
        free(q);
    }
    head = NULL;
}
 int judegeN_list(Link head)
 {
     if (head == NULL || head->next == NULL)
         return 1;
     else
         return -1;
 }
